def basic_sort(nums, start, end):
    temp = nums[start]

    j = start

    for i in range(start + 1, end + 1):
        if nums[i] < temp:
            nums[i], nums[j + 1] = nums[j + 1], nums[i]

    nums[start], nums[j] = nums[j], nums[start]

    return j


def bin_sort(nums, start, end):
    temp = nums[start]

    i = start + 1
    j = end

    while True:
        while i <= end and nums[i] < temp:
            i += 1
        while j >= start + 1 and nums[j] > temp:
            j -= 1

        if i > j: break

        nums[i], nums[j] = nums[j], nums[i]
        i += 1
        j -= 1
    nums[start], nums[j] = nums[j], nums[start]
    return j


def bin_search(nums, target):
    start = 0
    end = len(nums) - 1

    while start <= end:
        mid = start + (end - start) // 2
        if target == nums[mid]:
            return mid
        elif nums[mid] > target:
            end = mid - 1
        elif nums[mid] < target:
            start = mid + 1

    return -1


def left_bin_search(nums, target):
    start = 0
    end = len(nums)

    while start < end:
        mid = start + (end - start)
        if nums[mid] >= target:
            end = mid
        else:
            start = mid + 1

    return start


def right_bin_search(nums, target):
    start = 0
    end = len(nums)

    while start < end:
        mid = start + (end - start)
        if nums[mid] > target:
            end = mid
        else:
            start = mid + 1

    return start - 1


class TreeNode(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def pre_search(root: TreeNode):
    res = []

    if root is None:
        return res

    stack = [root]  # 使用的是栈
    while stack:
        p = stack.pop()
        res.append(p.val)
        if p.right:  # 先入右子树
            stack.append(p.right)
        if p.left:  # 后入左子树
            stack.append(p.left)
    return res


def level_search(root: TreeNode):
    ans = []

    if root is None:
        return ans

    queue = [root]  # 层序遍历使用的是队列

    while queue:
        top = queue.pop(0)
        ans.append(top.val)
        if top.left:  # 先进左子树
            queue.append(top.left)

        if top.right:  # 后进右子树
            queue.append(top.right)
    return ans


def mid_sarch(root: TreeNode):
    ans = []
    if root is None:
        return ans

    stack = []
    node = root
    while stack or node:  # 第一次通过node是否为空判断，后面都要通过stack判断
        # 先把左子树都入到头
        while node:
            stack.append(node)
            node = node.left
        # 此时 node 为空

        data = stack.pop()
        ans.append(data.val)
        node = data.right

    return ans


def post_search(root: TreeNode):
    ans = []
    if root is None:
        return ans

    stack = [root]  # 使用的栈

    while stack:
        p = stack.pop()
        ans.append(p.val)

        if p.left:  # 先入左子树
            stack.append(p.left)

        if p.right:  # 后入右子树
            stack.append(p.right)

    return ans.reverse()


class Node:
    def __init__(self, tree_node, depth):
        self.tree_node = tree_node
        self.depth = depth


class Solution:
    def maxDepth(self, root: TreeNode) -> int:

        ans = []
        if root is None:
            return []

        queue = [Node(root, 1)]
        lastLevel = 1
        last_level_ls = []

        while queue:
            top = queue.pop(0)

            depth = top.depth
            node = top.tree_node
            if depth == lastLevel:
                last_level_ls.append(node.val)
            else:
                ans.append(last_level_ls)
                lastLevel = depth
                last_level_ls = [node.val]

            if node.left:
                queue.append(Node(node.left, depth + 1))
            if node.right:
                queue.append(Node(node.right, depth + 1))
        ans.append(last_level_ls)
        return ans


class Solution:
    def lowestCommonAncestor(self, root, p, q):
        """
        核心思想：判断该分支下是否同时有两个节点之一，如果有返回
        :param root:
        :param p:
        :param q:
        :return:
        """

        if not root:
            return None

        # 如果
        if root == q or root == p:
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left is None:  # 从左子树无法找到公共父节点
            return right

        if right is None:  # 从右子树无法找到公共父节点
            return left

        if left and right:
            return root


class Solution:
    def binaryTreePaths(self, root: TreeNode):

        if root is None:
            return None

        ans = []

        queue = [(root, "" + str(root.val))]

        while queue:
            head, path = queue.pop(0)
            if not head.left and not head.right:
                ans.append(path)

            if head.left:
                queue.append((head.left, path + "->" + str(head.left.val)))

            if head.right:
                queue.append((head.right, path + "->" + str(head.right.val)))

        return ans


class Solution:
    def lowestCommonAncestor(self, root, p, q):
        def find_path(root, p):
            if root is None:
                return []

            queue = [(root, [root])]

            while queue:
                head, path = queue.pop(0)
                if head == p:
                    return path

                if head.left:
                    temp = path[:]
                    temp.append(head.left)
                    queue.append((head.left, temp))

                if head.right:
                    temp = path[:]
                    temp.append(head.right)
                    queue.append((head.right, temp))
            # 节点p不在树里面
            return []

        path_p = find_path(root, p)
        path_q = find_path(root, q)

        last = None
        while path_p and path_q:
            p = path_p.pop(0)
            q = path_q.pop(0)
            if p == q:
                last = p
            else:
                return last
        return last


class Solution:
    def inorderTraversal(self, root: TreeNode):
        WHITE, GRAY = 0, 1
        res = []
        stack = [(WHITE, root)]
        while stack:
            color, node = stack.pop()
            if color == WHITE:
                if node.right:
                    stack.append((WHITE, node.right))
                stack.append((GRAY, node))
                if node.left:
                    stack.append((WHITE, node.left))
            else:
                res.append(node.val)
        return res
